关于《数据结构》学科
《数据结构》是一门研究数值计算的程序设计问题的学科。
和具有相同的增长速度。
is .
仅基于比较的算法能得到的最好的“最坏时间复杂度”是。
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。
将个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是。
线性表L如果需要频繁地进行不同下标元素的插入、删除操作，此时选择顺序存储结构更好。
若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。
循环队列也存在空间溢出的问题。
在实现二项式队列时，每棵二项式树是用左孩子右兄弟的结构表示的。
已知一棵二叉树的先序遍历结果是ABC, 则CAB不可能是中序遍历结果。
若一个结点是某二叉树的中序遍历序列的最后一个结点，则它必是该树的前序遍历序列中的最后一个结点。
存在一棵总共有2016个结点的二叉树，其中有16个结点只有一个孩子。
任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）。
二叉搜索树的查找和折半查找的时间复杂度相同。
对AVL树中的任一结点，其左子树的高度一定比其右子树的高度要高。
若一棵平衡二叉树的所有非叶结点的平衡因子都是0，则其必为完美二叉树。
任何最小堆中从根结点到任一叶结点路径上的所有结点是有序的（从小到大）。
关于哈夫曼树
哈夫曼树中一定没有度为 1 的结点。
对于一个有个结点、条边的森林，不能确定它共有几棵树。
无向连通图边数一定大于顶点个数减1。
用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。
Prim 算法是维护一个森林，每一步把两棵树合并成一棵。
Prim 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。
如果 是有权无向图 唯一的一条最短边，那么边 一定会在该图的最小生成树上。
若图G为连通图且不存在拓扑排序序列，则图G必有环。
对个记录进行快速排序，在最坏的情况下，其时间复杂度是。
对个记录进行归并排序，归并趟数的数量级是。
若用平方探测法解决冲突，则插入新元素时，若散列表容量为质数，插入就一定可以成功。
在散列表中，所谓同义词就是被不同散列函数映射到同一地址的两个元素。
KMP算法的特点是在模式匹配时指示主串的指针不会变小回溯。
根据数据元素之间的关系的不同特性，通常分为哪几类基本结构？
链表 - 时间复杂度
在包含 个数据元素的链表中，▁▁▁▁▁ 的时间复杂度为 。
以下哪些项是栈元素操作的基本特点：
数据结构由数据的
对于给定的有向图如下，则每个顶点的入度和出度顺次为：
填写格式：入度1/出度1 入度2/出度2 ... 入度6/出度6，相邻两顶点答案用 1 个空格分隔，不得有多余符号。
例如：0/1 2/3 4/5 6/0 1/2 3/4
给定一组整数：
{ 36, 25, 81, 17, 49 }
采用简单选择排序法按升序排序，请写出从左往右执行一趟排序后的结果：
{ 1分, 1分, 1分, 1分, 1分 }
下列代码的功能是将存有N个元素的数组A[]调整为最小堆。
#define leftchild(i) ( 2*(i)+1 )
void BuildMinHeap( ElementType A[], int N )
{ int i, j, child;
ElementType Tmp;
for ( i = (N-1)/2; i >= 0; i-- ) {
j = i;
for ( Tmp = A[j]; leftchild(j) < N; j = child ) {
child = leftchild(j);
if (3分)
child ++;
if (3分) A[j] = A[child];
else break;
}
3分;
}
}
感谢燕山大学窦燕老师修正题目！
下列代码的功能是将大顶堆H中指定位置P上的元素的整数键值上调D个单位，然后继续将H调整为大顶堆。
void IncreaseKey( int P, int D, PriorityQueue H )
{
int i, key;
key = H->Elements[P] + D;
for ( i = 3分; H->Elements[i/2] < key; i/=2 )
3分;
H->Elements[i] = key;
}
下列代码的功能是对一个给定的图G执行拓扑排序，其中TopNum[]从1开始记录拓扑序。
void Topsort( Graph G )
{
Queue Q;
Vertex V, W;
NodePtr ptr;
int counter = 0;
Q = CreateEmptyQueue(NumVertex);
for ( V=0; V<G->NumV; V++ )
if ( Indegree[V] == 0 )
Enqueue(V, Q);
while ( !IsEmpty(Q) ){
V = Dequeue( Q );
TopNum[V] = 3分;
for ( ptr=G->List[V]; ptr; ptr=ptr->Next) {
W = ptr->Vertex;
if ( 3分 == 0 )
Enqueue(W, Q);
}
}
if ( counter != NumVertex )
printf("ERROR: Graph has a cycle.\n");
DisposeQueue(Q);
}
下列代码的功能是计算给定二叉树T的宽度。二叉树的宽度是指各层结点数的最大值。函数Queue_rear和Queue_front分别返回当前队列Q中队尾和队首元素的位置。
typedef struct TreeNode *BinTree;
struct TreeNode
{
int Key;
BinTree Left;
BinTree Right;
};
int Width( BinTree T )
{
BinTree p;
Queue Q;
int Last, temp_width, max_width;
temp_width = max_width = 0;
Q = CreateQueue(MaxElements);
Last = Queue_rear(Q);
if ( T == NULL) return 0;
else {
Enqueue(T, Q);
while (!IsEmpty(Q)) {
p = Front_Dequeue(Q);
3分;
if ( p->Left != NULL ) Enqueue(p->Left, Q);
3分;
if ( Queue_front(Q) > Last ) {
Last = Queue_rear(Q);
if ( temp_width > max_width ) max_width = temp_width;
3分;
} /* end-if */
} /* end-while */
return max_width;
} /* end-else */
}